package com.lw.leetcode.other.c;

import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * 68. 文本左右对齐
 *
 * @author liw
 * @version 1.0
 * @date 2022/6/22 10:55
 */
public class FullJustify {

    public static void main(String[] args) {
        FullJustify test = new FullJustify();

        //   "This    is    an",
        //   "example  of text",
        //   "justification.  "
        String[] arr = {"This", "is", "an", "example", "of", "text", "justification."};
        int k = 16;

        //  "What   must   be",
        //  "acknowledgment  ",
        //  "shall be        "
//        String[] arr = {"What", "must", "be", "acknowledgment", "shall", "be"};
//        int k = 16;

        //  "Science  is  what we",
        //  "understand      well",
        //  "enough to explain to",
        //  "a  computer.  Art is",
        //  "everything  else  we",
        //  "do                  "
//        String[] arr = {"Science", "is", "what", "we", "understand", "well", "enough", "to", "explain", "to", "a", "computer.", "Art", "is", "everything", "else", "we", "do"};
//        int k = 20;

        List<String> list = test.fullJustify(arr, k);
        for (String s : list) {
            System.out.println(s + "&");
        }
    }

    private String[] words;
    private int maxWidth;

    public List<String> fullJustify(String[] words, int maxWidth) {
        int length = words.length;
        this.words = words;
        this.maxWidth = maxWidth;
        int index = 0;
        List<String> list = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        while (index < length) {
            sb.setLength(0);
            Node node = find(index);
            list.add(add(node, sb));
            index = node.end + 1;
        }
        return list;
    }

    private String add(Node node, StringBuilder sb) {
        int st = node.st;
        int end = node.end;
        sb.append(words[st]);
        if (node.flag == 1) {
            for (int i = st + 1; i <= end; i++) {
                sb.append(' ');
                sb.append(words[i]);
            }
            for (int i = sb.length(); i < maxWidth; i++) {
                sb.append(' ');
            }
            return sb.toString();
        }
        int len = node.len;
        int count = end - st;
        if (count == 0) {
            for (int i = 0; i < len; i++) {
                sb.append(' ');
            }
            return sb.toString();
        }

        int value = len / count + 1;
        int value2 = value - 1;
        int max = len % count;
        for (int i = st + 1; i <= end; i++) {
            if (max > 0) {
                max--;
            } else {
                value = value2;
            }
            for (int j = 0; j < value; j++) {
                sb.append(' ');
            }
            sb.append(words[i]);
        }
        return sb.toString();
    }

    private Node find(int index) {
        int length = words.length;
        int count = 0;
        int len = 0;
        int st = index;
        while (index < length) {
            String word = words[index];
            int l = word.length();
            len += l;
            count++;
            if (len + count - 1 > maxWidth) {
                return new Node(st, index - 1, 0, maxWidth - len + l);
            }
            index++;
        }
        return new Node(st, length - 1, 1, 0);
    }

    private static class Node {
        private int st;
        private int end;
        private int flag;
        private int len;

        public Node(int st, int end, int flag, int len) {
            this.st = st;
            this.end = end;
            this.flag = flag;
            this.len = len;
        }
    }

}
